export type Convert2TreeOptionsType = {
  primaryFieldName?: string
  parentFieldName?: string
  childrenFieldName?: string
  isPath?: boolean
  pathFieldName?: string
  isClearTag?: boolean
}

/**
 * 数组转化成的树形结构数组中节点的类型
 */
export type Convert2TreeNodeType = Record<string, any>

/**
 * Convert2Tree 方法返回值中树形结构数组的类型
 */
export type Convert2TreeReturnTreeType = Array<Convert2TreeNodeType>

/**
 * Convert2Tree 方法返回值类型中主键与树形结构数组节点之间映射的类型
 */
export type Convert2TreeReturnMapType = Record<any, Convert2TreeNodeType>

/**
 * Convert2Tree 方法返回值类型
 */
export type Convert2TreeReturnType = {
  tree: Convert2TreeReturnTreeType
  map: Convert2TreeReturnMapType
}

/**
 * 将数组转化为树形结构数组，在转化成树形结构数组的过程中，子级元素会被添加到父级元素中指定存放
 * 子级节点的数组属性中
 *
 * @param {Array<Record<string, any>>} arr 原始数组
 * @param {Convert2TreeOptionsType} options 配置选项
 * - primaryFieldName 原始数组中元素的主键字段名，默认为 'id'
 * - parentFieldName 原始数组中元素指向父级的字段名，默认为 'parent'
 * - childrenFieldName 转化成树形结构数组中元素节点存放子级节点的数组属性名，默认为 'children'
 * - isPath 是否需要生成从根节点到当前子级节点的路径，默认为 false，生成的路径是由当前子级节
 * 点的主键值加上所有父级节点的主键值组成的数组，如果当前节点为根节点，则路径为空数组
 * - pathFieldName 需要生成从根节点到当前子级节点的路径时，用于存储路径数据的字段名，默认为 'path'
 * - isClearTag 是否需要清除原始数组中对象元素中的标记字段，默认为 `false`，在将数组转化为树形
 * 结构数组的过程中，对于处理完成的对象元素会在其上添加一个标记字段 `_handled`，标记该对象元素
 * 已被处理过
 * @returns {Convert2TreeReturnType} 树形结构数组和映射表组成的对象，其中 tree 为树形结
 * 构数组，map 为映射表，映射表的 key 为数组元素的主键值，映射表的 value 为转化成树形结构数组
 * 中的节点元素
 */
export const convert2Tree = (
  arr: Array<Record<string, any>>,
  options: Convert2TreeOptionsType = {}
): Convert2TreeReturnType => {
  const {
    primaryFieldName,
    parentFieldName,
    childrenFieldName,
    isPath,
    pathFieldName,
    isClearTag
  } = {
    primaryFieldName: 'id',
    parentFieldName: 'parent',
    childrenFieldName: 'children',
    isPath: false,
    pathFieldName: 'path',
    isClearTag: false,
    ...options
  }

  /**
   * 将具有父级的节点添加到父级节点的子级数组中
   *
   * @param node 当前处理中的节点
   * @param parent 当前处理中的节点的父级
   * @param item 当前遍历到的原始数组中的元素
   */
  const itemHasParentAdd2Parent = (
    node: Convert2TreeNodeType,
    parent: Convert2TreeNodeType,
    item: Record<string, any>
  ) => {
    // 如果需要生成路径，则给当前节点添加路径字段，将父级的路径数组与当前节点的主键值拼接成新的路
    // 径数组作为当前节点的路径字段值
    if (isPath) node[pathFieldName] = [...parent[pathFieldName], node[primaryFieldName]]
    // 将当前节点添加到父级的子级数组中
    parent[childrenFieldName].push(map[node[primaryFieldName]])
    // 标记当前数组元素已处理
    item._handled = true
  }

  /**
   * 原始数组元素的处理函数
   *
   * @param item 当前遍历到的原始数组元素
   * @param index 当前遍历到的原始数组元素的索引
   */
  const itemHandler = (item: Record<string, any>, index: number) => {
    // 根据当前遍历的元素生成树形结构中的节点
    const node: Record<string, any> & { children: Convert2TreeNodeType[] } = { ...item, children: [] }
    // 映射表中添加当前节点
    map[node[primaryFieldName]] = node
    // 如果当前节点没有父级
    if (!node[parentFieldName]) {
      // 如果需要生成路径，则给当前节点添加路径字段，由于当前节点没有父级，所以路径为仅包含当前
      // 节点的主键值的数组
      if (isPath) node[pathFieldName] = [node[primaryFieldName]]
      // 直接添加到最终结果数组中
      result.push(node)
      // 标记当前数组元素已处理
      item._handled = true
    }
    // 如果当前遍历的元素有父级
    else {
      itemHasParentHandler(node, item, index)
    }
  }

  /**
   * 具有父级的原始数组元素的处理函数
   *
   * @param node 当前处理中的节点
   * @param item 当前遍历到的原始数组元素
   * @param index 当前遍历到的原始数组元素的索引
   */
  const itemHasParentHandler = (
    node: Convert2TreeNodeType,
    item: Record<string, any>,
    index: number
  ) => {
    // 在映射表中寻找当前节点的父级
    let parent = map[node[parentFieldName]]
    // 如果在映射表中找到父级
    if (parent) itemHasParentAdd2Parent(node, parent, item)
    // 如果在映射表中没有找到父级
    else {
      // 从前向后遍历到当前数组元素的过程中没有出现当前节点的父级，说明当前节点的父级可能在当前
      // 数组元素的后面，所以从当前数组元素的后面开始，寻找当前节点的父级，提前处理当前节点的父级
      for (let i = index + 1; i < arr.length; i++) {
        const iitem = arr[i]
        // 如果当前遍历的元素已处理过，则跳过
        if (iitem._handled) continue
        // 如果不为父级
        if (iitem[primaryFieldName] !== node[parentFieldName]) continue
        // 如果是父级元素，先提前对父级元素进行处理
        itemHandler(iitem, i)
        // 在映射表中找到提前处理完成的父级
        parent = map[node[parentFieldName]]
        // 将当前节点添加到父级的子级数组中
        itemHasParentAdd2Parent(node, parent, item)
        // 找到当前节点的父级，退出当前函数的执行
        return
      }
      // 如果从当前数组元素的后面开始，寻找当前节点的父级，仍然没有找到，还存在一种可能，树形结
      // 构层次较多，有些遍历到但不是当前节点的父节点，可能是父节点的父节点，发生了跳跃，所以从
      // 当前数组元素的后面开始，仍然没有找到时，从当前数组元素的前面开始，寻找当前节点的父级
      for (let i = index - 1; i >= 0; i--) {
        const iitem = arr[i]
        // 如果当前遍历的元素已处理过，则跳过
        if (iitem._handled) continue
        // 如果不为父级
        if (iitem[primaryFieldName] !== node[parentFieldName]) continue
        // 如果是父级元素，先提前对父级元素进行处理
        itemHandler(iitem, i)
        // 在映射表中找到提前处理完成的父级
        parent = map[node[parentFieldName]]
        // 将当前节点添加到父级的子级数组中
        itemHasParentAdd2Parent(node, parent, item)
        // 找到当前节点的父级，退出当前函数的执行
        return
      }
      // 循环执行结束，还未找到当前节点的父级，则说明当前节点的父级不存在，则直接将当前节点添加
      // 到最终结果数组中
      result.push(node)
      // 标记当前数组元素已处理
      item._handled = true
    }
  }

  // 最终要返回的树形结构结果数组
  const result: Convert2TreeReturnTreeType = []
  // 主键与最终要返回的树形结构结果数组中的元素之间的映射
  const map: Convert2TreeReturnMapType = {}
  // 将原先的数组转化为树形结构
  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    // 如果当前数组元素已处理过，则跳过
    if (item._handled) continue
    // 处理当前数组元素
    itemHandler(item, i)
  }
  // 如果需要清除标记字段，则遍历原始数组，删除标记字段
  if (isClearTag) {
    arr.forEach((item) => {
      Reflect.deleteProperty(item, '_handled')
    })
  }
  // 返回最终的树形结构结果数组以及主键与最终要返回的树形结构结果数组中的元素之间的映射
  return {
    tree: result,
    map
  }
}

export type Convert2TreeType = typeof convert2Tree
